package searchable;

import binaria.BinaryTree;
import iterator.Iterator;
import tree.PrePostVisitor;
import tree.Tree;
import visitor.Visitor;
import enumeration.Enumeration;
import wrapper.Chr;
import wrapper.Comparable;
import wrapper.Dbl;
import wrapper.Int;
import wrapper.Str;

public class BinarySearchTree extends BinaryTree implements SearchTree {
	private BinarySearchTree getLeftBST() {
		return (BinarySearchTree) getLeft();
	}

	private BinarySearchTree getRightBST() {
		return (BinarySearchTree) getRight();
	}

	public Comparable find(Comparable object) {
		if (isEmpty())
			return null;
		int diff = object.compare((Comparable) getKey());
		if (diff == 0)
			return (Comparable) getKey();
		else if (diff < 0)
			return getLeftBST().find(object);
		else
			return getRightBST().find(object);
	}

	public Comparable findMin() {
		if (isEmpty())
			return null;
		else if (getLeftBST().isEmpty())
			return (Comparable) getKey();
		else
			return getLeftBST().findMin();
	}

	public void insert(Comparable object) {
		if (isEmpty())
			attachKey(object);
		else {
			int diff = object.compare((Comparable) getKey());
			if (diff == 0)
				throw new IllegalArgumentException("duplicate key");
			if (diff < 0)
				getLeftBST().insert(object);
			else
				getRightBST().insert(object);
		}
		++count;
	}

	public void attachKey(Object object) {
		if (!isEmpty())
			try {
				throw new InvalidOperationException();
			} catch (InvalidOperationException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		key = object;
		left = new BinarySearchTree();
		right = new BinarySearchTree();
	}

	public void withdraw(Comparable object) {
		if (isEmpty())
			throw new IllegalArgumentException("object not found");
		int diff = object.compare((Comparable) getKey());
		if (diff == 0) {
			if (!getLeftBST().isEmpty()) {
				Comparable max = (Comparable) getLeftBST().findMax();
				key = max;
				getLeftBST().withdraw(max);
			} else if (!getRightBST().isEmpty()) {
				Comparable min = getRightBST().findMin();
				key = min;
				getRightBST().withdraw(min);
			} else {
				detachKey();
				--count;
			}
		} else if (diff < 0)
			getLeftBST().withdraw(object);
		else
			getRightBST().withdraw(object);
	}

	public Object getKey() {
		return key;
	}

	public boolean isEmpty() {
		if (count == 0)
			return true;
		else
			return false;
	}

	public boolean isLeaf() {
		if (getLeft().isEmpty()) {
			if (getRight().isEmpty())
				return true;
			else
				return false;
		} else
			return false;
	}

	@Override
	public int getDegree() {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public int getHeight() {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public void depthFirstTraversal(PrePostVisitor visitor) {
		// TODO Auto-generated method stub

	}

	@Override
	public void breadthFirstTraversal(Visitor visitor) {
		// TODO Auto-generated method stub

	}

	@Override
	public int getCount() {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public boolean isFull() {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public void purge() {
		// TODO Auto-generated method stub

	}

	@Override
	public void accept(Visitor visitor) {
		// TODO Auto-generated method stub

	}

	@Override
	public Enumeration getEnumeration() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Iterator getIterator() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean isMember(Comparable object) {
		// TODO Auto-generated method stub
		return false;
	}

	public Object detachKey() {
		if (!isLeaf())
			try {
				throw new InvalidOperationException();
			} catch (InvalidOperationException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		Object result = key;
		key = null;
		left = right = null;
		return result;
	}

	@Override
	public Comparable findMax() {
		if (isEmpty())
			return null;
		else if (getRightBST().isEmpty())
			return (Comparable) getKey();
		else
			return getRightBST().findMax();
	}

	public void printTree() {
		if (!isEmpty()) {
			printSubTree(getLeft());
			
			if (key.getClass().equals(new Int(0).getClass())) {
				System.out.print(((Int) key).getValue() + ", ");
			} else if (key.getClass().equals(new Chr(' ').getClass())) {
				System.out.print(((Chr) key).getValue() + ", ");
			} else if (key.getClass().equals(new Dbl(0).getClass())) {
				System.out.print(((Dbl) key).getValue() + ", ");
			} else {
				System.out.print(((Str) key).getValue() + ", ");
			}
			
			printSubTree(getRight());
		}
	}
	
	public void printVisitorTree(Visitor visitor)
	{
		if(!(left==null) && !getLeft().isEmpty()) ((BinarySearchTree) getLeft()).printVisitorTree(visitor);
		visitor.visit(key);
		if(!(left==null) && !getRight().isEmpty()) ((BinarySearchTree) getRight()).printVisitorTree(visitor);
	}

	public void printSubTree(BinaryTree subtree) {
		if (!subtree.isEmpty()) {
			printSubTree(subtree.getLeft());
			
			if (key.getClass().equals(new Int(0).getClass())) {
				System.out.print(((Int) subtree.getKey()).getValue() + ", ");
			} else if (key.getClass().equals(new Chr(' ').getClass())) {
				System.out.print(((Chr) subtree.getKey()).getValue() + ", ");
			} else if (key.getClass().equals(new Dbl(0).getClass())) {
				System.out.print(((Dbl) subtree.getKey()).getValue() + ", ");
			} else {
				System.out.print(((Str) subtree.getKey()).getValue() + ", ");
			}
			
			printSubTree(subtree.getRight());
		}
	}
}